package com.zyk.leetcode;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/5/10 15:48
 */
public class M1009 {

    // 暴力解
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int R = matrix.length, C = matrix[0].length;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (matrix[i][j] == target)
                    return true;
            }
        }
        return false;
    }

    // 数据量在差不多 (10^6) 时才比下边的快
    // 二分: 左至右, 上至下升序. == target返回, < target往下找, > target往左找
    public static boolean searchMatrix2(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int R = matrix.length, C = matrix[0].length;

        int l = 0, r = C - 1, u = 0, d = R - 1;
        int col = 0, row = 0;
        while (l <= r) {
            while (l <= r) {
                col = (l + r) >> 1;
                if (matrix[row][col] == target) {
                    return true;
                } else if (matrix[row][col] < target) {   // < target. 右边
                    l = col + 1;
                } else {     // 左边
                    r = col - 1;
                }
            }
            while (u <= d) {
                row = (u + d) >> 1;
                if (matrix[row][col] == target) {
                    return true;
                } else if (matrix[row][col] < target) { // 下边
                    u = row + 1;
                } else {     // 上边
                    d = row - 1;
                }
            }
        }
        while (row >= 0 && row < R && col >= 0 && col < C) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {   // 去左边
                col--;
            } else {     // 去下边
                row++;
            }
        }
        return false;
    }

    public static boolean searchMatrix3(int[][] matrix, int target) {
        int m = matrix.length;
        if(m == 0) return(false);
        int n = matrix[0].length;
        int i = 0, j = n - 1;
        while(i < m && j >= 0){
            if(matrix[i][j] == target) return(true);
            else if(matrix[i][j] < target) i++;
            else j--;
        }
        return(false);
    }

    public static void main(String[] args) {
        /*int[][] matrix = {
                {1,  4,  7,  11, 15},
                {2,  5,  8,  12, 19},
                {3,  6,  9,  16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };
        int target = 26;*/
        /*int[][] matrix = {
                {1, 1}
        };
        int target = 2;
        System.out.println(searchMatrix(matrix, target));
        System.out.println(searchMatrix2(matrix, target));*/

        int times = 1000;
        int maxRow = 100000;
        int maxCol = 100000;
        int maxInterval = 5;
        for (int i = 0; i < times; i++) {
            int[][] m = generateRandomArr(maxRow, maxCol, maxInterval);
            System.out.println("===========size :" + (m.length != 0 ? m.length * m[0].length : 0) + "==================");
            int target = 1;
            long s1 = System.nanoTime();
            boolean ans1 = searchMatrix(m, target);
            long s2 = System.nanoTime();
            boolean ans2 = searchMatrix2(m, target);
            long s3 = System.nanoTime();
            boolean ans3 = searchMatrix3(m, target);
            long s4 = System.nanoTime();
            if ( (ans1 ^ ans2) || (ans1 ^ ans3)) {     //  不能一个为true, 一个为false
                System.out.println("OOPS");
                for (int[] nums : m) {
                    System.out.println(Arrays.toString(nums));
                }
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println(ans3);
                break;
            }
            System.out.println("暴力解: " + (s2 - s1));
            System.out.println("先二分找到基础位置, 在通过单步跳动: " + (s3 - s2));
            System.out.println("二分: " + (s4 - s3));
            System.out.println("=================================");
        }
    }

    // 生成一个测试数组, 要求: 每一行都是由小变大, 每一列都是由小变大
    public static int[][] generateRandomArr(int maxRow, int maxCol, int maxInterval) {
        int R = (int) (Math.random() * maxRow + 1);     // 能够达到maxRow, 同时又可能为0
        int C = (int) (Math.random() * maxCol + 1);
        int[][] res = new int[R][C];
        if (R == 0 || C == 0) return res;
        res[0][0] = (int) (Math.random() * 10);
        // 先填第一行
        for (int c = 1; c < C; c++) {
            res[0][c] = res[0][c - 1] + (int) (Math.random() * maxInterval) + 1;
        }
        // 再填第一列
        for (int r = 1; r < R; r++) {
            res[r][0] = res[r - 1][0] + (int) (Math.random() * maxInterval) + 1;
        }
        // 每一个值都要比左边上边要大
        for (int r = 1; r < R; r++) {
            for (int c = 1; c < C; c++) {
                int base = Math.max(res[r - 1][c], res[r][c - 1]);
                res[r][c] = base + (int) (Math.random() * maxInterval) + 1;
            }
        }
        return res;
    }

}
